import java.util.Stack;

public class Sort {
    public void selectSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for(int j = i + 1;j < array.length;j++){
                if(array[minIndex] > array[j])
                    minIndex = j;
            }
            int tmp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = tmp;
        }
    }

    public void swap(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public void selectSort2(int[] array){
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int minIndex = left;
            int maxIndex = left;
            for(int i = left + 1;i <= right;i++){
                if(array[minIndex] > array[i])
                    minIndex = i;
                if(array[maxIndex] < array[i])
                    maxIndex = i;
            }
            swap(array,left,minIndex);
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }



    public static void main(String[] args) {
        int[] a = {2,3,12,4,3,2};
        Sort sort = new Sort();
        sort.selectSort(a);
        for(int i = 0;i < a.length;i++){
            System.out.print(a[i]+" ");
        }
        StringBuilder builder = new StringBuilder();
        Stack<Integer> stack = new Stack<>();

    }


    //第一种：快速排序，挖坑法，无优化版本
    //每一趟的操作，交换，填坑
    private static int partition1(int[] array, int left, int right) {
        int tmp = array[left];//保存最左位置的值
        //开始找坑
        //多次左右走
        while (left < right) {
            //先右往左走，找一个值比tmp小的，一次循环或者说一次向右走
            // 这里必须要是 >= ，不然当下标0和下标array.length的话，就会陷入死循环，这两个下标的值一直在交换
            //提问：为什么不需要再次++，去进入循环呢？
            while (left < right && array[right] >= tmp)
                right--;
            array[left] = array[right];
            //从左往右走，找一个值比tmp大的，一次循环或者说一次向左走
            while (left < right && array[left] <= tmp)
                left++;
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    //快速排的的非递归形式
    public static void quickSortNor(int[] array){
        int left = 0;
        int right = array.length - 1;
        int pivot = partition1(array,left,right);
        Stack<Integer> stack = new Stack<>();
        if(pivot - 1>left){
            stack.push(left);
            stack.push(pivot - 1);
        }
        if(pivot + 1 < right){
            stack.push(pivot + 1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            left = stack.pop();
            right = stack.pop();
            pivot = partition1(array,left,right);
            if(pivot - 1>left){
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(pivot + 1 < right){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }


}
